Computer programs include a plurality of tasks that are executed in a particular sequence and time determined by logic of the corresponding source code and constraints of the processing hardware used. Computer systems and, in particular, ones incorporating multiple processing elements can achieve faster execution of these computer programs and yet be rational in their demand for processing hardware resources provided they incorporate a method that is efficient in task organization for execution of tasks comprising said computer programs.
Task organization generally refers to logical assignment of priority among tasks or processes in an execution queue. Identification of execution units in input code and organizing execution thereof to achieve faster, yet accurate, execution of said source code are critical parameters deciding the multitasking efficiency and processing capacity of multi/parallel processing systems and especially, real time operating systems. Devising task organizing methods tailor-made for multiple processing environments has been a pressing need of the art.
The part of operating systems which provides the task organizing function is known as the task organizer. Responsibility of a task organizer is to allocate CPU time for execution of tasks/threads/processes in case of single CPU systems. These task organizers generally implement time sharing policies, where CPU time slot is allotted to each process/task/thread for execution. In case of systems with multiple CPUs the task organizer is expected to distribute tasks among different processing elements in such a way that the load is balanced among CPUs and/or execution time is minimized. The challenges faced for writing better task organizing methods are minimizing synchronization and communication times among dependent tasks, optimizing execution time, optimizing resource or CPU utilization, etc.
In this regard, various prior art references have attempted to address said problems through means such as representing a repetitive sequence of execution in the form of a tiled sequence with the aim to reduce data contention and to maximize the locality of data among them; method that identifies parallelizable tasks and organizing them on different processing units; and a method for parallelization and organizing that is based on distributing tasks of different levels obtained by dividing a total processing time by synchronizing time points in a time sequential order. Other few means includes a method that combines pre-run-time and run-time techniques; method comprising a cluster of embedded processors that share a common code distribution bus; and organizing tasks based on resource requirements of the task.
However, there are drawbacks of the methods in the existing prior art such as the overall efficiency of the parallel processing system is not achieved and methods are restricted to either static or dynamic organizing of tasks. Further, methods depend on architectural feedback and fail to determine the optimized organizing of tasks in terms of number of processing elements used. Also, the methods neither provide the optimal number of processing elements required to organize given tasks, nor provides organization of tasks that is optimized in terms of processing element utilization. Furthermore, the methods does not consider data dependency, function call charts, mapping of available processing elements and other related parameters and thus, fails to accurately arrive at optimized organization of execution of tasks.
Information relevant to attempts to address these problems can be found in EP1416385, EP533445, US20070143759, US20070255929, U.S. Pat. No. 5,452,461, U.S. Pat. No. 7,165,252, US20080263555, U.S. Pat. No. 6,292,822, US20070192545, US20070113038 and US20080263555. However, each one of these references suffers from one or more of the above listed drawbacks.
Therefore, the hitherto available methods have not been able to satisfactorily address said problems of the state of the art. Therefore, there exists a need for a method to address the drawbacks by providing a method for enabling static as well as dynamic reorganizing of tasks which serves for optimal use of execution resources and execution time.